package week02

// 146. LRU 缓存机制
// https://leetcode-cn.com/problems/lru-cache/

type ListNode struct {
	key int
	value int
	pre *ListNode
	next *ListNode
}

type LRUCache struct {
	kv map[int]*ListNode
	head *ListNode
	tail *ListNode
	capacity int
}


func Constructor(capacity int) LRUCache {
	head := &ListNode{}
	tail := &ListNode{}
	head.next = tail
	tail.pre = head

	return LRUCache {
		kv: make(map[int]*ListNode, capacity),
		capacity: capacity,
		head: head,
		tail: tail,
	}
}


func (this *LRUCache) Get(key int) int {
	if node, ok := this.kv[key]; ok {
		this.insertToHead(node)
		return node.value
	}
	return -1
}


func (this *LRUCache) Put(key int, value int)  {
	if node, ok := this.kv[key]; ok {
		node.value = value
		this.insertToHead(node)
	} else {
		node = this.newNode(key, value)
		this.insertToHead(node)
	}
	if len(this.kv) > this.capacity {
		this.removeTail()
	}
}

func (this *LRUCache) newNode(key, value int) *ListNode {
	return &ListNode{
		key: key,
		value: value,
	}
}

func (this *LRUCache) insertToHead(node *ListNode) {
	if node.pre != nil && node.next != nil {
		node.pre.next = node.next
		node.next.pre = node.pre
	}
	next := this.head.next
	this.head.next = node
	next.pre = node
	node.pre = this.head
	node.next = next
	this.kv[node.key] = node
}

func (this *LRUCache) removeTail() *ListNode {
	node := this.tail.pre
	node.pre.next = this.tail
	this.tail.pre = node.pre
	delete(this.kv, node.key)
	return node
}